package a09_贪心算法;

//32
//求解关键
//发现32不符合要求，因为需要递增
//首先十位上的数字必须-1，因为十位不变的话，个位变成1和0还是递减
//22、23、24、25、26、27、28、29都满足，取最大值29

//规则：如果发现两位不符合要求，我们需要对前一位进行-1，这样后一位才有大于前一位的可能。
//后一位就应该取最大的。这样才能让得到的数值是最大的。

import java.util.Arrays;

//遍历顺序：
//332
//从前往后：33符合，看32，不符合，29，加上前面的329，不符合最终要求
//为啥不行：因为是递增，前面处理完后，后面有可能变小，导致不符合最终要求
public class a22_单调递增的数字 {

    public static void main(String[] args) {
        int i = monotoneIncreasingDigits(100);
        System.out.println();
    }

    public static int monotoneIncreasingDigits(int n) {
        char[] chars = String.valueOf(n).toCharArray();
        int flag = chars.length;
        for (int i = chars.length - 1; i >= 1; i--) {
            if(chars[i-1] > chars[i]){
                chars[i-1] = (char)((Integer.valueOf(chars[i-1] + "") - 1) + '0');
                flag = i;
            }
        }
        for (int i = flag; i < chars.length; i++) {
            chars[i] = '9';
        }
        return Integer.valueOf(new String(chars));
    }

//    public static int monotoneIncreasingDigits(int n) {
//        char[] chars = String.valueOf(n).toCharArray();
//        for (int i = chars.length - 1; i >= 1; i--) {
//            if(chars[i-1] > chars[i]){
//                chars[i-1] = (char)((Integer.valueOf(chars[i-1] + "") - 1) + '0');
//                chars[i] = '9';
//            }
//        }
//        return Integer.valueOf(new String(chars));
//    }
}
